class Solution:
    def combinationSum4(self, nums, target: int) -> int:
        dp = {0:1}
        nums.sort()
        sumTime = 0
        while dp:
            tmp = {}
            for key in dp.keys():
                for i in range(len(nums)):
                    if i != 0 and nums[i] == nums[i - 1]:
                        continue
                    nowSum = key + nums[i]
                    if nowSum == target:
                        sumTime+=dp[key]
                        break
                    elif nowSum > target:
                        break
                    else:
                        tmp.setdefault(nowSum, 0)
                        tmp[nowSum] += dp[key]
            dp = tmp

        return sumTime

if __name__ == '__main__':
    so = Solution()
    nums = [3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25]
    target = 10
    r = so.combinationSum4(nums, target)
    print(r)
